{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Add Minimum Number of Rungs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addRungs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #新增的最少台阶数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>严格递增</strong> 的整数数组 <code>rungs</code> ，用于表示梯子上每一台阶的 <strong>高度</strong> 。当前你正站在高度为 <code>0</code> 的地板上，并打算爬到最后一个台阶。</p>\n",
    "\n",
    "<p>另给你一个整数 <code>dist</code> 。每次移动中，你可以到达下一个距离你当前位置（地板或台阶）<strong>不超过</strong> <code>dist</code> 高度的台阶。当然，你也可以在任何正 <strong>整数</strong> 高度处插入尚不存在的新台阶。</p>\n",
    "\n",
    "<p>返回爬到最后一阶时必须添加到梯子上的 <strong>最少</strong> 台阶数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rungs = [1,3,5,10], dist = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：\n",
    "</strong>现在无法到达最后一阶。\n",
    "在高度为 7 和 8 的位置增设新的台阶，以爬上梯子。 \n",
    "梯子在高度为 [1,3,5,<strong><em>7</em></strong>,<strong><em>8</em></strong>,10] 的位置上有台阶。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rungs = [3,6,8,10], dist = 3\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "这个梯子无需增设新台阶也可以爬上去。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rungs = [3,4,6,7], dist = 2\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "现在无法从地板到达梯子的第一阶。 \n",
    "在高度为 1 的位置增设新的台阶，以爬上梯子。 \n",
    "梯子在高度为 [<strong><em>1</em></strong>,3,4,6,7] 的位置上有台阶。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rungs = [5], dist = 10\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>这个梯子无需增设新台阶也可以爬上去。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= rungs.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= rungs[i] <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 <= dist <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>rungs</code> <strong>严格递增</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [add-minimum-number-of-rungs](https://leetcode.cn/problems/add-minimum-number-of-rungs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [add-minimum-number-of-rungs](https://leetcode.cn/problems/add-minimum-number-of-rungs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,5,10]\\n2', '[3,6,8,10]\\n3', '[3,4,6,7]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        rungs = [0] + rungs\n",
    "        result = 0\n",
    "        for i in range(1, len(rungs)):\n",
    "            result += math.ceil((rungs[i]-rungs[i-1])/dist) - 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        rungs = [0] + rungs\n",
    "        for a, b in pairwise(rungs):\n",
    "            ans += (b - a + dist - 1) // dist - 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        count = 0\n",
    "        rungs = [0] + rungs\n",
    "        n = len(rungs)\n",
    "        for i in range(1, n):\n",
    "            diff = rungs[i]-rungs[i-1]\n",
    "            if diff > dist:\n",
    "                count += (diff-1)//dist\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        rungs = [0] + rungs\n",
    "        for x, y in pairwise(rungs):\n",
    "            if y - x > dist:\n",
    "                ans += (y - x - 1) // dist\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        last_h = 0\n",
    "        for r in rungs:\n",
    "            ans += int((r - 0.01 - last_h) // dist)\n",
    "            last_h = r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        rungs.insert(0, 0)\n",
    "        for a, b in pairwise(rungs):\n",
    "            ans += (b-a-1) // dist\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        rungs = [0] + rungs\n",
    "        ans = 0\n",
    "        for x, y in pairwise(rungs):\n",
    "            ans += (y - x + dist - 1) // dist - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        start = 0\n",
    "        res = 0\n",
    "        for i in range(len(rungs)):\n",
    "            if i == 0 :\n",
    "                tmp = rungs[0] \n",
    "                if dist < tmp:\n",
    "                    if tmp%dist!=0:\n",
    "                        res += int(floor(rungs[0]/dist))\n",
    "                    else:\n",
    "                        res += int(floor(rungs[0]/dist))-1\n",
    "                    \n",
    "            #i!=0\n",
    "            #i-1到不了i：\n",
    "            if i>0 and rungs[i]-rungs[i-1]>dist:\n",
    "                tmp = rungs[i]-rungs[i-1]\n",
    "                if tmp%dist!=0:\n",
    "                    res += int(floor((rungs[i]-rungs[i-1])/dist))\n",
    "                else:\n",
    "                    res += int(floor((rungs[i]-rungs[i-1])/dist))-1\n",
    "            #print(res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(rungs)-1):\n",
    "            ans += (rungs[i+1] - rungs[i] - 1) // dist\n",
    "        return ans + (rungs[0] - 1) // dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        curr=0\n",
    "        add=0\n",
    "        i=0\n",
    "        for h in rungs:\n",
    "            d=h-curr\n",
    "            add+=(h-curr-1)//dist\n",
    "            curr=h\n",
    "        return(add)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        c=0\n",
    "        rungs.insert(0,0)\n",
    "        n=len(rungs)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        else:\n",
    "            for i in range(1,n):\n",
    "                if (rungs[i]-rungs[i-1])%dist==0:\n",
    "                    c+=(rungs[i]-rungs[i-1])//dist -1\n",
    "                else:\n",
    "                    c+=(rungs[i]-rungs[i-1])//dist\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        if rungs[0] != 0:\n",
    "            rungs = [0] + rungs\n",
    "        for a, b in pairwise(rungs):\n",
    "            ans += (b-1-a) // dist\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for i in rungs:\n",
    "            if i - cur > dist:\n",
    "                res += math.ceil((i - cur) / dist) - 1\n",
    "            cur = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        rungs.insert(0, 0)\n",
    "        return sum((b-a-1) // dist for a, b in pairwise(rungs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        c=0\n",
    "        rungs.insert(0,0)\n",
    "        n=len(rungs)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        else:\n",
    "            for i in range(1,n):\n",
    "                if (rungs[i]-rungs[i-1])%dist==0:\n",
    "                    c+=(rungs[i]-rungs[i-1])//dist -1\n",
    "                else:\n",
    "                    c+=(rungs[i]-rungs[i-1])//dist\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        i,n,ans = 0,len(rungs),0\n",
    "        if rungs[0]%dist==0:\n",
    "            ans += rungs[0]//dist-1\n",
    "        else:\n",
    "            ans += rungs[0]//dist\n",
    "        while i<n-1:\n",
    "            if rungs[i]+dist<rungs[i+1]:\n",
    "                if (rungs[i+1]-rungs[i])%dist==0:\n",
    "                    ans += (rungs[i+1]-rungs[i])//dist-1\n",
    "                else:\n",
    "                    ans += (rungs[i+1]-rungs[i])//dist\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        c=0\n",
    "        rungs.insert(0,0)\n",
    "        n=len(rungs)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        else:\n",
    "            for i in range(1,n):\n",
    "                if (rungs[i]-rungs[i-1])%dist==0:\n",
    "                    c+=(rungs[i]-rungs[i-1])//dist -1\n",
    "                else:\n",
    "                    c+=(rungs[i]-rungs[i-1])//dist\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        i,n,ans = 0,len(rungs),0\n",
    "        if rungs[0]%dist==0:\n",
    "            ans += rungs[0]//dist-1\n",
    "        else:\n",
    "            ans += rungs[0]//dist\n",
    "        while i<n-1:\n",
    "            if rungs[i]+dist<rungs[i+1]:\n",
    "                if (rungs[i+1]-rungs[i])%dist==0:\n",
    "                    ans += (rungs[i+1]-rungs[i])//dist-1\n",
    "                else:\n",
    "                    ans += (rungs[i+1]-rungs[i])//dist\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        if rungs[0] != 0:\n",
    "            rungs = [0] + rungs\n",
    "        for a, b in pairwise(rungs):\n",
    "            ans += (b-1-a) // dist\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        if rungs[0] != 0:\n",
    "            rungs = [0] + rungs\n",
    "        for a, b in pairwise(rungs):\n",
    "            ans += (b-1-a) // dist\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        c=0\n",
    "        rungs.insert(0,0)\n",
    "        n=len(rungs)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        else:\n",
    "            for i in range(1,n):\n",
    "                if (rungs[i]-rungs[i-1])%dist==0:\n",
    "                    c+=(rungs[i]-rungs[i-1])//dist -1\n",
    "                else:\n",
    "                    c+=(rungs[i]-rungs[i-1])//dist\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        c=0\n",
    "        rungs.insert(0,0)\n",
    "        n=len(rungs)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        else:\n",
    "            for i in range(1,n):\n",
    "                if (rungs[i]-rungs[i-1])%dist==0:\n",
    "                    c+=(rungs[i]-rungs[i-1])//dist -1\n",
    "                else:\n",
    "                    c+=(rungs[i]-rungs[i-1])//dist\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        result = 0\n",
    "        base = 0\n",
    "        for rung in rungs:\n",
    "            if rung - base <= dist: base = rung\n",
    "            else:\n",
    "                a = (rung - base)/dist\n",
    "                if a%1 == 0: result += (a-1)\n",
    "                else: result += math.floor(a)\n",
    "                base = rung\n",
    "        return int(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: [int], dist: int) -> int:\n",
    "        #dp[i] 表示到达第i个节点处需要新增的最小数目\n",
    "        rungs.insert(0,0)\n",
    "        nn=len(rungs)\n",
    "        dp=[sys.maxsize for i in range(nn)]\n",
    "        dp[0]=0\n",
    "        for i in range(1,nn):\n",
    "            if rungs[i-1]+dist>=rungs[i]:\n",
    "                dp[i]=dp[i-1]\n",
    "                continue\n",
    "            tmp=(rungs[i]+dist-1-rungs[i-1])//dist\n",
    "            dp[i]=dp[i-1]+tmp-1\n",
    "\n",
    "        return dp[nn-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        cont = 0\n",
    "        stairs = [0]\n",
    "        for i in rungs:\n",
    "            stairs.append(i)\n",
    "        for j in range(len(stairs)-1):\n",
    "            dis = stairs[j+1] - stairs[j]\n",
    "            if dis > dist:\n",
    "                if dis%dist == 0:\n",
    "                    cont += (dis//dist)-1\n",
    "                else:\n",
    "                    cont += dis//dist\n",
    "        return cont"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        n=len(rungs)\n",
    "        count=0\n",
    "        ans=[]\n",
    "        ans.append(0)\n",
    "        for i in range(n):\n",
    "            ans.append(rungs[i])\n",
    "\n",
    "        for i in range(n):\n",
    "            tmp=ans[i+1]-ans[i]\n",
    "            if tmp>dist:\n",
    "                count=math.ceil(tmp/dist)-1 + count\n",
    "\n",
    "        return count\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "\n",
    "        i = 0\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "\n",
    "        # 3 - 9,3\n",
    "        # 3 - 10, 3. 3,6,9,10\n",
    "        for i in range(len(rungs)):\n",
    "            if cur + dist >= rungs[i]:\n",
    "                cur = rungs[i]\n",
    "            else:\n",
    "                div, mod = divmod(rungs[i] - cur, dist)\n",
    "                ans += div - (mod == 0)\n",
    "                cur = rungs[i]\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans, pre = 0, 0\n",
    "        for h in rungs:\n",
    "            if (d := h - pre) > dist:\n",
    "                ans += (d - 1) // dist # 等价于 ceil(d / dist) - 1\n",
    "            pre = h\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        x = 0\n",
    "        fh = 0\n",
    "        for i in rungs:\n",
    "            if x+dist < i:\n",
    "                fh += (i-x)//dist - (0 if (i-x)%dist else 1)\n",
    "            x = i\n",
    "        return fh"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs, dist: int) -> int:\n",
    "        pose = 0\n",
    "        count = 0\n",
    "        for step in rungs:\n",
    "            if step - pose > dist:\n",
    "                count+=(step - pose-1)//dist\n",
    "            pose = step\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        ans += (rungs[0] - 1) // dist \n",
    "        for i in range(len(rungs) - 1):\n",
    "            ans += (rungs[i+1] - rungs[i] - 1) // dist \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        res = 0   # 需要增设的梯子数目\n",
    "        curr = 0   # 当前高度\n",
    "        for h in rungs:\n",
    "            # 遍历数组计算高度差和最少添加数目，并更新当前高度\n",
    "            # d = h - curr\n",
    "            res += (h - curr - 1) // dist\n",
    "            curr = h\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = (rungs[0] - 1) // dist\n",
    "        for i in range(1, len(rungs)):\n",
    "            if rungs[i] - rungs[i-1] > dist:\n",
    "                ans += (rungs[i] - rungs[i-1] - 1) // dist\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for i in rungs:\n",
    "            ans += (i - cur) // dist - (((i - cur) % dist) == 0)\n",
    "            cur = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        cur = ans = 0\n",
    "        for i in rungs:\n",
    "            ans += (i - cur - 1) // dist\n",
    "            cur = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        t=(rungs[0]-1)//dist\n",
    "        for i in range(len(rungs)-1):\n",
    "            t+=(rungs[i+1]-rungs[i]-1)//dist\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = (rungs[0] - 1) // dist\n",
    "        for i in range(1, len(rungs)):\n",
    "            ans += (rungs[i] - rungs[i-1] - 1) // dist\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        ans += (rungs[0] - 1) // dist \n",
    "        for i in range(len(rungs) - 1):\n",
    "            ans += (rungs[i+1] - rungs[i] - 1) // dist \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for i in rungs:\n",
    "            ans += (i - cur) // dist\n",
    "            if (i - cur) % dist == 0:\n",
    "                ans -= 1\n",
    "            cur = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "            count = pre = 0\n",
    "            for item in rungs:\n",
    "                count += (item - pre - 1) // dist\n",
    "                pre = item\n",
    "            return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs, dist: int) -> int:\n",
    "        pose = 0\n",
    "        count = 0\n",
    "        for step in rungs:\n",
    "            if step - pose > dist:\n",
    "                count+=(step - pose-1)//dist\n",
    "            pose = step\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for i in rungs:\n",
    "            if i - cur > dist:\n",
    "                ans += (i - cur) // dist\n",
    "                if (i - cur) % dist == 0:\n",
    "                    ans -= 1\n",
    "            cur = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        a = 0\n",
    "        l = 0\n",
    "        for i in rungs:\n",
    "            dif = i - a\n",
    "            if dif <= dist:\n",
    "                a = i\n",
    "                continue\n",
    "            else:\n",
    "                if dif % dist == 0:\n",
    "                    taijie = dif // dist - 1\n",
    "                else:\n",
    "                    taijie = dif // dist\n",
    "                l += taijie\n",
    "            a = i\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 模拟 + 贪心\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        res = 0   # 需要增设的梯子数目\n",
    "        curr = 0   # 当前高度\n",
    "        for h in rungs:\n",
    "            # 遍历数组计算高度差和最少添加数目，并更新当前高度\n",
    "            res += (h - curr - 1) // dist\n",
    "            curr = h\n",
    "\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        res = 0   # 需要增设的梯子数目\n",
    "        curr = 0   # 当前高度\n",
    "        for h in rungs:\n",
    "            # 遍历数组计算高度差和最少添加数目，并更新当前高度\n",
    "        \n",
    "            res += (h - curr - 1) // dist\n",
    "            curr = h\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for h in rungs:\n",
    "            ans += (h-cur-1)//dist\n",
    "            cur = h\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans=0\n",
    "        last_max=0\n",
    "        for it in rungs:\n",
    "            if(last_max+dist>=it):\n",
    "                last_max=it\n",
    "            else:\n",
    "                ans+=(it-last_max-1)//dist\n",
    "                last_max=it\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        x = 0\n",
    "        fh = 0\n",
    "        for i in rungs:\n",
    "            if x+dist < i:\n",
    "                fh += (i-x)//dist - (0 if (i-x)%dist else 1)\n",
    "            x = i\n",
    "        return fh"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        return sum((b-a-1) // dist for a, b in pairwise(chain([0], rungs)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        start = ret = 0\n",
    "        for i in rungs:\n",
    "            if i - start > dist:\n",
    "                t = (i- start - 1) // dist\n",
    "                ret += t\n",
    "            start = i\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        # 公式咋推导的？\n",
    "        start = 0\n",
    "        res = 0\n",
    "        for h in rungs:\n",
    "            if h - start > dist:\n",
    "                t = (h-start-1)//dist\n",
    "                res += t\n",
    "            start = h\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        ht = 0\n",
    "        for h in rungs:\n",
    "            ans += (h - ht - 1) // dist\n",
    "            ht = h\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        return sum((b-a-1) // dist for a, b in pairwise([0] + rungs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        # 公式咋推导的？\n",
    "        #(h - ht - 1) // dist ：减一的原因是，恰好是dist的k倍话，只要k-1个梯子，比如1和5之间只要一个dist=2的梯子（在3处），在前面-1能起到恰好k倍时最终结果-1的效果\n",
    "\n",
    "        start = 0\n",
    "        res = 0\n",
    "        for h in rungs:\n",
    "            if h - start > dist:\n",
    "                t = (h-start-1)//dist\n",
    "                res += t\n",
    "            start = h\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        l = 0\n",
    "        result = 0\n",
    "        for r in rungs:\n",
    "            if (r - l) % dist == 0:\n",
    "                result -= 1\n",
    "            result += (r - l) // dist\n",
    "            l = r\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        pre = 0\n",
    "        res = 0\n",
    "        for i in range(len(rungs)):\n",
    "            diff = rungs[i] - pre \n",
    "            if diff > dist:\n",
    "                res += diff//dist - 1\n",
    "                if diff%dist > 0:\n",
    "                    res += 1\n",
    "            pre = rungs[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        now=0\n",
    "        ans=0\n",
    "        for i in range(len(rungs)):\n",
    "            if rungs[i]-now<=dist:\n",
    "                now = rungs[i]\n",
    "            else:\n",
    "                ans+=ceil((rungs[i]-now)/dist)-1\n",
    "                now = rungs[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        new_rungs=[0]+rungs\n",
    "        t=0\n",
    "        dif_rungs=[new_rungs[i+1]-new_rungs[i] for i in range(len(new_rungs)-1)]\n",
    "        for i in dif_rungs:\n",
    "            if i>dist:\n",
    "                if i%dist==0:\n",
    "                    t+=i/dist-1\n",
    "                else:    \n",
    "                    t+=math.floor(i/dist)\n",
    "        return int(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        result = 0\n",
    "        pre = 0\n",
    "        for i in range(len(rungs)):\n",
    "            if(pre + dist >= rungs[i]):\n",
    "                pre = rungs[i]\n",
    "            else:\n",
    "                if((rungs[i]-pre) % dist == 0):\n",
    "                    result += (rungs[i]-pre) // dist - 1\n",
    "                else:\n",
    "                    result += (rungs[i]-pre) // dist\n",
    "                pre = rungs[i]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        ht = 0\n",
    "        for h in rungs:\n",
    "            ans += (h - ht - 1) // dist\n",
    "            ht = h\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        if len(rungs) == 0:\n",
    "            return 0\n",
    "        tmpNum, ans = 0, 0\n",
    "        for i in range(0, len(rungs)):\n",
    "            if rungs[i] - tmpNum <= dist:\n",
    "                tmpNum = rungs[i]\n",
    "                continue\n",
    "            tmp = 0\n",
    "            if (rungs[i] - tmpNum) % dist == 0:\n",
    "                tmp = 1\n",
    "            ans += (rungs[i] - tmpNum) // dist - tmp\n",
    "            tmpNum = rungs[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        rungs = [0] + rungs\n",
    "        ans = 0\n",
    "        for x, y in pairwise(rungs):\n",
    "            if y - x > dist:\n",
    "               ans += (y - x + dist - 1) // dist - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        new_rungs=[0]+rungs\n",
    "        t=0\n",
    "        for i in range(len(rungs)):\n",
    "            dif_value=new_rungs[i+1]-new_rungs[i]\n",
    "            if dif_value>dist:\n",
    "                if dif_value%dist==0:\n",
    "                    t+=dif_value/dist-1\n",
    "                else:    \n",
    "                    t+=math.floor(dif_value/dist)\n",
    "        return int(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        def f(x, y):\n",
    "            if (y-x) % dist:\n",
    "                return (y-x) // dist\n",
    "            else:\n",
    "                return (y-x) // dist - 1\n",
    "        ans = f(0, rungs[0])\n",
    "        for i in range(1, len(rungs)):\n",
    "            ans += f(rungs[i-1], rungs[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        pre = 0\n",
    "        res = 0\n",
    "        for r in rungs:\n",
    "            diff = r - pre\n",
    "            if diff > dist:\n",
    "                add = diff//dist if diff%dist!=0 else (diff//dist-1)\n",
    "                res += add\n",
    "            pre = r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(rungs) + 1\n",
    "        rungs = [0] + rungs\n",
    "        for i in range(n):\n",
    "            temp = rungs[i] - rungs[i - 1]\n",
    "            if temp > dist:\n",
    "                if temp % dist:\n",
    "                    ans += temp // dist\n",
    "                else:\n",
    "                    ans += temp // dist - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def addRungs(self, rungs: List[int], dist: int) -> int:\n",
    "        res = cur = 0\n",
    "        for i in range(len(rungs)):\n",
    "            r = rungs[i]\n",
    "            if cur + dist >= r:\n",
    "                cur = r\n",
    "            else:\n",
    "                res = res + math.ceil((r - dist - cur)/dist)\n",
    "                cur = r\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
